Bloom Filter for Web Scraping Deduplication: Principle, Python, and Redis

A Bloom Filter for web scraping deduplication solves a common problem in crawler systems: fast existence checks across massive datasets. It is especially useful when you can tolerate a small false-positive rate, such as preventing cache penetration, URL deduplication, and large-scale “seen-before” checks.

To understand the idea quickly, start with a classic “minimum mice” thought experiment. Then, we will connect that logic to Bloom Filters and finish with a practical Bloom Filter for web scraping deduplication implementation in Python and Redis.

Outbound references (docs):

• Bloom filter (concept overview)
• RedisBloom commands

What problem does a Bloom Filter solve?

In large-scale scraping, you often need to answer one question quickly:

• “Have I already crawled this URL (or item) before?”

A traditional set or database index works, but it consumes more memory and may slow down under heavy concurrency. In contrast, a Bloom Filter uses a compact bit array and hash functions. As a result, it can handle large-scale existence checks with very low memory cost.

This is why a Bloom Filter for web scraping deduplication becomes a popular choice in distributed crawler systems.

The 7 mice problem and the Bloom Filter intuition

Imagine 100 bottles of liquid. One bottle contains poison, and a single drop kills a mouse within 24 hours. You want to identify the poisoned bottle in one day, using the fewest mice.

Instead of using 100 mice, you can solve it with only 7 mice, because:

• 7 bits can represent up to 2⁷ = 128 values.
• 100 bottles fit inside that range.

Step 1: Encode bottles in binary (7 bits)

• Bottle 1 → 0000001
• Bottle 10 → 0001010

Step 2: Feed based on bit positions

Assign Mouse 1–Mouse 7 to the 7 bit positions. Then:

• Mouse 1 drinks from bottles where bit 1 is 1
• Mouse 2 drinks from bottles where bit 2 is 1
• …and so on

Step 3: Decode deaths after 24 hours

• Dead mouse → that bit is 1
• Alive mouse → that bit is 0

For example, if Mice 2, 4, 5, and 7 die, the binary result is:

0101101 → decimal 45 → Bottle 45 is poisoned.

This demonstrates the core idea: you can represent a large search space using compact bits. Likewise, a Bloom Filter stores membership hints inside a bit array.

How Bloom Filters work

A Bloom Filter has two main parts:

1. A bit array (each position is 0 or 1)
2. Multiple hash functions (or a hash function with multiple seeds)

Add an element

1. Compute k hash values
2. Map them into bit array positions
3. Set those bits to 1

Check existence

1. Compute the same k hashes
2. If any bit is 0, the element definitely does not exist
3. If all bits are 1, the element probably exists

Key conclusion:

• “Not exists” is always correct.
• “Exists” can be wrong (false positive).

That false-positive possibility is the trade-off for speed and memory savings in a Bloom Filter for web scraping deduplication.

Pros and cons of Bloom Filters

Pros

• Very memory efficient (bit-level storage)
• Very fast inserts and queries
• Great for large-scale existence checks

Cons

• False positives are unavoidable
• Deleting elements is difficult in the classic design
• False positives increase as you add more items

Python Bloom Filter implementation (bitarray + mmh3)

Install dependencies:

pip install bitarray mmh3

Implementation:

from bitarray import bitarray
import mmh3

class BloomFilter(set):
    def __init__(self, size: int, hash_count: int):
        super().__init__()
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)
        self.size = size
        self.hash_count = hash_count

    def add(self, item: str):
        for i in range(self.hash_count):
            index = mmh3.hash(item, i) % self.size
            self.bit_array[index] = 1
        return self

    def __contains__(self, item: str) -> bool:
        return all(
            self.bit_array[mmh3.hash(item, i) % self.size]
            for i in range(self.hash_count)
        )

# Usage
bloom = BloomFilter(size=100, hash_count=10)
urls = ["www.baidu.com", "www.qq.com", "www.jd.com"]

for url in urls:
    bloom.add(url)

print("www.baidu.com" in bloom)  # True
print("www.fake.com" in bloom)   # False (or rarely True)

Tip: increase size and tune hash_count when you store more URLs, because that reduces false positives.

Redis integration for distributed deduplication

A single-machine Bloom Filter works well, but distributed crawlers need shared state. Therefore, Redis Bloom Filter support is a common upgrade path.

Install client:

pip install redis

Example (RedisBloom commands):

import redis

r = redis.Redis(host="localhost", port=6379, db=0)

# Create Bloom filter:
# error_rate=0.01, capacity=100000
r.execute_command("BF.RESERVE", "myBloomFilter", 0.01, 100000)

# Add and check
items = ["url1", "url2"]
for item in items:
    r.execute_command("BF.ADD", "myBloomFilter", item)

print(r.execute_command("BF.EXISTS", "myBloomFilter", "url1"))  # 1
print(r.execute_command("BF.EXISTS", "myBloomFilter", "urlX"))  # 0 (usually)

In a real distributed workflow, replace localhost with your shared Redis host. Then every crawler node uses the same Bloom Filter state, so deduplication stays consistent.

Conclusion

A Bloom Filter for web scraping deduplication provides an efficient trade-off: it dramatically reduces memory usage and keeps existence checks fast, while accepting a small false-positive rate. With Python, you can implement it locally in minutes. With Redis, you can scale the same idea across distributed crawler clusters.